{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 网络流\n",
    "\n",
    "**Highlight**\n",
    "- $MAXN$ $MAXM$ 分清楚\n",
    "- 使用 ^1 建立反向边时\n",
    "    - 边要从偶数开始编号\n",
    "    - ***空间要开两倍大！！！***\n",
    "- 最大流消耗流量，反向边要增加流量\n",
    "- $spfa$ 或 $bfs$ 增广路时只增广还有容量的边\n",
    "- 最大流一次 $bfs$ 后可以跑多次 $dinic$ ,但费用流一次 $spfa$ 只能 $Update$ 一次\n",
    "- 三分图匹配中间的点要拆成一个入点一个出点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 最大流\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "const int MAXN, MAXM;\n",
    "int head[MAXN], now[MAXN], dis[MAXN];\n",
    "int ver[MAXM], nxt[MAXM], cap[MAXM];\n",
    "int tot = 1, s, t;\n",
    "\n",
    "inline void AddSingleEdge(int u, int v, int w)\n",
    "{\n",
    "    tot++, nxt[tot] = head[u], head[u] = tot, ver[tot] = v, cap[tot] = w;\n",
    "}\n",
    "inline void AddEdge(int u, int v, int w)\n",
    "{\n",
    "    AddSingleEdge(u, v, w);\n",
    "    AddSingleEdge(v, u, 0);\n",
    "}\n",
    "\n",
    "bool bfs()\n",
    "{\n",
    "    memcpy(now, head, sizeof(head));\n",
    "    memset(dis, 0x00, sizeof(dis));\n",
    "    queue<int> que;\n",
    "    que.push(s), dis[s] = 1;\n",
    "    while (que.size())\n",
    "    {\n",
    "        auto u = que.front();\n",
    "        que.pop();\n",
    "        for (auto e = head[u]; e; e = nxt[e])\n",
    "        {\n",
    "            auto v = ver[e];\n",
    "            if (!dis[v] && cap[e])\n",
    "            {\n",
    "                dis[v] = dis[u] + 1;\n",
    "                if (v == t)\n",
    "                    return true;\n",
    "                que.push(v);\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "    return false;\n",
    "}\n",
    "\n",
    "int dinic(int u, int flow)\n",
    "{\n",
    "    if (u == t)\n",
    "        return flow;\n",
    "    auto rest = flow;\n",
    "    auto e = now[u];\n",
    "    for (; e && rest; e = nxt[e])\n",
    "    {\n",
    "        auto v = ver[e];\n",
    "        if (dis[v] == dis[u] + 1 && cap[e])\n",
    "        {\n",
    "            auto subFlow = dinic(v, min(rest, cap[e]));\n",
    "            rest -= subFlow;\n",
    "            cap[e] -= subFlow;\n",
    "            cap[e ^ 1] += subFlow;\n",
    "            if (subFlow == 0)\n",
    "                dis[v] = 0;\n",
    "        }\n",
    "    }\n",
    "    now[u] = e;\n",
    "    return flow - rest;\n",
    "}\n",
    "\n",
    "int main()\n",
    "{\n",
    "    int maxFlow = 0, flow;\n",
    "    while (bfs())\n",
    "        while (flow = dinic(s, INT_MAX))\n",
    "            maxFlow += flow;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 费用流"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "const int MAXN,MAXM;\n",
    "int n, m, s, t;\n",
    "int head[MAXN],dis[MAXN], incf[MAXN], vis[MAXN], pre[MAXN];\n",
    "int ver[MAXM], nxt[MAXM], cap[MAXM], cost[MAXM];\n",
    "int tot = 1\n",
    "int sum_cost, sum_flow;\n",
    "inline void AddSingleEdge(int u, int v, int w, int c)\n",
    "{\n",
    "    tot++;\n",
    "    nxt[tot] = head[u];\n",
    "    wei[tot] = w;\n",
    "    cost[tot] = c;\n",
    "    to[tot] = v;\n",
    "    head[u] = tot;\n",
    "}\n",
    "inline void AddEdge(int u, int v, int w, int c)\n",
    "{\n",
    "    AddSingleEdge(u, v, w, c);\n",
    "    AddSingleEdge(v, u, 0, -c);\n",
    "}\n",
    "bool spfa()\n",
    "{\n",
    "    memset(dis, 0x7f, sizeof dis);\n",
    "    memset(vis, 0x00, sizeof vis);\n",
    "    queue<int> q;\n",
    "    dis[s] = 0;\n",
    "    q.push(s);\n",
    "    vis[s] = true;\n",
    "    incf[s] = INT_MAX;\n",
    "    while (q.size()) {\n",
    "        auto u = q.front();\n",
    "        q.pop();\n",
    "        vis[u] = false;\n",
    "        for (auto i = head[u]; i; i = nxt[i]) {\n",
    "            auto v = to[i];\n",
    "            if (wei[i] && dis[v] > dis[u] + cost[i]) {\n",
    "                dis[v] = dis[u] + cost[i];\n",
    "                incf[v] = min(incf[u], wei[i]);\n",
    "                if (!vis[v])\n",
    "                    vis[v] = true, q.push(v);\n",
    "                pre[v] = i;\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "    return dis[t] != 0x7f7f7f7f;\n",
    "}\n",
    "void Update()\n",
    "{\n",
    "    auto u = t;\n",
    "    while (u != s) {\n",
    "        auto e = pre[u];\n",
    "        wei[e] -= incf[t];\n",
    "        wei[e ^ 1] += incf[t];\n",
    "        u = to[e ^ 1];\n",
    "    }\n",
    "    sum_cost += dis[t] * incf[t];\n",
    "    sum_flow += incf[t];\n",
    "}\n",
    "int main()\n",
    "{\n",
    "    while (spfa())\n",
    "        Update();\n",
    "}\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
